//
//  LinkList.cpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/4/3.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#include "LinkList.hpp"

// 初始化单链表
bool InitList(LinkList &L)
{
    L = (LNode*)malloc(sizeof(LNode));
    if (L==NULL)
        return false;
    L->next = NULL;
    return true;
}

// 判断是否为空表
bool isEmpty(LinkList L)
{
    return L->next == NULL;
}

// 插入
bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1)
        return false;
    LNode *p = GetElem(L, i - 1);
    return InsertNextNode(p, e);
}

// 在节点之后插入
bool InsertNextNode(LNode *p, int e)
{
    if (p == NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 在节点之前插入
bool InsertPriorNode(LNode *p, int e)
{
    if (p == NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->data = p->data;
    p->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 删除
bool ListDelete(LinkList &L, int i, int &e)
{
    if (i < 1)
        return false;
    LNode *p = GetElem(L, i - 1);
    if (p == NULL || p->next == NULL)
        return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

// ✨按位查找
LNode * GetElem(LinkList L, int i)
{
    if (i < 0)
        return NULL; // i = 0获取头节点
    int j = 0; // j为指针p的位置
    LinkList p = L;
    while (j < i && p) {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找
LNode * LocateElem(LinkList L, int e)
{
    LNode *p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}

// 求长度
int length(LinkList L)
{
    LNode *p = L->next;
    int len = 0;
    while (p != NULL) {
        p = p->next;
        len++;
    }
    return len;
}

// 尾插法
LinkList ListTailInsert(LinkList &L)
{
    InitList(L);
    int x;
    LNode *s, *r;
    r = L;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

// 头插法
LinkList ListHeadInsert(LinkList &L)
{
    InitList(L);
    int x;
    LNode *s;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

// ✨单链表逆序
LinkList ListReverse(LinkList &L)
{
    LNode *p = L->next;
    LNode *r = p;
    L->next = NULL;
    while (p != NULL) {
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }
    return L;
}

// 打印
void PrintList(LinkList L)
{
    LNode *p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
